import re
import cgi
import copy

#from lxml import etree
from elementtree import ElementTree as etree


# Basic regexp for matching all expressions in a template.
TOKEN = r"([\w_:-]+)(\[\d+\])*"
EXPR = re.compile(r"\{(%s(\.%s)*)\}" % (TOKEN, TOKEN))


class Template(object):
    def __init__(self, template=None, parser=None, tree=None):
        if tree is not None:
            self.tree = tree
        else:
            parser = parser or etree.XML
            self.tree = parser(template)

    def render(self, context=None, remove_empty_nodes=True, escape=True):
        # Get all namespaces available in the template.
        nstree = _get_namespaces(self.tree)

        context = context or {}
        tree = search(copy.deepcopy(self.tree), context, '', nstree,
                remove_empty_nodes, escape)

        tree = apply(tree, "%SHRUBBERY_OPEN_TAG%", "{")
        tree = apply(tree, "%SHRUBBERY_CLOSE_TAG%", "}")

        return Template(tree=tree)
    process = render

    def __str__(self):
        return etree.tostring(self.tree)


def search(tree, data, ns, nstree, remove_empty_nodes, escape):
    # Search for all expressions inside a given namespace.
    regexp = re.compile(r"\{%s.*\}" % re.escape(ns.rstrip('.')))
    nodes = find_nodes(tree, regexp)
    if not nodes: return tree

    # Find common ancestor and clone it for each element in data.
    node, parent = find_common_ancestor(nodes, tree)
    wrapped = False
    if not parent:
        # Wrap tree.
        tree = parent = etree.Element('Document')
        parent.append(node)
        wrapped = True
    index = list(parent).index(node)

    # Apply replacement data.
    if not isinstance(data, list): data = [data]
    data = [v for v in data if v not in [None, {}, []]]
    if data or remove_empty_nodes: parent.remove(node)
    for i, values in enumerate(data):
        repl = apply(copy.deepcopy(node),
                "\{%s\}" % re.escape(ns.rstrip('.')),
                values, escape)
        parent.insert(index+i, repl)

        keys = nstree.keys()
        keys.sort()
        keys.reverse()
        for k in keys:
            new_ns = '%s%s.' % (ns, k)
            new_nstree = nstree.get(k)

            # Get any indexes.
            indexes = re.match(TOKEN, k)
            k, slice_ = indexes.groups()

            try:
                subdata = values.get(k)
            except:
                subdata = getattr(value, k, None)
            if slice_ and subdata:
                subdata = subdata[int(slice_[1:-1])]

            repl = search(parent, subdata, new_ns, new_nstree,
                    remove_empty_nodes, escape)

    if wrapped:
        return tree[0]
    else:
        return tree


def apply(tree, match, data, escape=True):
    regexp = re.compile(match)
    nodes = find_nodes(tree, regexp)

    # Normalize data.
    if isinstance(data, (int, long, float)):
        data = unicode(data)
    elif isinstance(data, str):
        data = data.decode('utf-8')
    elif not isinstance(data, unicode):
        data = u''

    data = EXPR.sub(lambda m:
            "%%SHRUBBERY_OPEN_TAG%%%s%%SHRUBBERY_CLOSE_TAG%%"
            % m.group(1), data)

    for node in nodes:
        if escape:
            if node.text:
                node.text = regexp.sub(data, node.text)
            if node.tail:
                node.tail = regexp.sub(data, node.tail)
        else:
            wrapper = etree.XML('<Document>%s</Document>' % regexp.sub(data, etree.tostring(node)))
            new = wrapper[0]
            node[:] = new[:]
            node.text = new.text
            node.tail = new.tail

        if node.attrib:
            for k, v in node.attrib.items():
                node.attrib[k] = regexp.sub(data, v).strip()
                if not node.attrib[k]: del node.attrib[k]
    return tree


def find_common_ancestor(nodes, tree, parent=None):
    for child in tree:
        candidate = True
        # Check if all nodes are descendants of this one.
        for node in nodes:
            if node not in child.getiterator():
                candidate = False
        if candidate: return find_common_ancestor(nodes, child, tree)
    return tree, parent
    

def _get_namespaces(tree):
    namespaces = {}
    for node in tree.getiterator():
        if node.text:
            for ns in EXPR.findall(node.text):
                ns = ns[0].split('.')
                root = namespaces
                for item in ns:
                    root = root.setdefault(item, {})
        if node.tail:
            for ns in EXPR.findall(node.tail):
                ns = ns[0].split('.')
                root = namespaces
                for item in ns:
                    root = root.setdefault(item, {})
        if node.attrib:
            for k, v in node.attrib.items():
                for ns in EXPR.findall(v):
                    ns = ns[0].split('.')
                    root = namespaces
                    for item in ns:
                        root = root.setdefault(item, {})
    return namespaces


def find_nodes(tree, regexp):
    nodes = []
    for node in tree.getiterator():
        if node.text and regexp.search(node.text):
            nodes.append(node)
        elif node.tail and regexp.search(node.tail):
            nodes.append(node)
        elif node.attrib:
            for k, v in node.attrib.items():
                if regexp.search(v):
                    nodes.append(node)
                    break
    return nodes


if __name__ == '__main__':
    t = Template("""<ul><li>{a}</li></ul>""")
    print etree.tostring(t.render({"a": range(4)}))
    t = Template("""<div><p class="{entry.verb}">I {entry.verb} {entry.noun}.</p></div>""")
    print etree.tostring(t.render({"entry": {"verb": "like", "noun": "<b>Python</b>"}}, escape=False))
